package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.HeapProblem;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author tzp
 * @since 2020/10/14
 */
public class LC215 implements HeapProblem {
    public int findKthLargest(int[] nums, int k) {
        List<Integer> list = new LinkedList<>();
        for (int num : nums) {
            if (list.size() < k) {
                addToSortList(list, num);
            } else {
                if (num > list.get(0)) {
                    addToSortList(list, num);
                    list.remove(0);
                }
            }
        }
        return list.get(0);
    }

    public static void addToSortList(List list, int a) {
        int i1 = Collections.binarySearch(list, a);
        if (i1 < 0) i1 = -(i1 + 1);
        list.add(i1, a);
    }

    public static void main(String[] args) {
        int[] a = {3, 2, 1, 5, 6, 4};
        System.out.println(new LC215().findKthLargest(a, 1));
        System.out.println(new LC215().findKthLargest(a, 2));
        System.out.println(new LC215().findKthLargest(a, 3));
        System.out.println(new LC215().findKthLargest(a, 4));
    }
}
